class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int len = profit.size();
        const int mod = 1e9 + 7;

        // 下面是利用滚动数组进行空间优化的写法
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
        for(int j = 0; j <= n; j++)
            dp[j][0] = 1;
        for(int i = 1; i <= len; i++)
        {
            for(int j = n; j >= group[i - 1]; j--)
            {
                for(int k = minProfit; k >= 0; k--)
                {
                    dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[j][k] %= mod;
                }
            }
        }
        return dp[n][minProfit];

        // 我们把group和profit合起来称为计划
        // dp[i][j][k]表示在前i个计划中挑选，人数不超过j，利润至少为k的计划组合数
        // vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
        
        // dp[0][j][0]表示在0个计划中选，人数不超过j，利润至少为0的情况，那么只有一种情况，就是啥都不选，所以初始化为1
        // 其余情况都是0，比如dp[0][j][k]，表示在0个计划中选，人数不超过j，利润至少为k的情况，那啥都不选也不行了，所以就是0
        // for(int j = 0; j <= n; j++)
        //     dp[0][j][0] = 1;

        // for(int i = 1; i <= len; i++)
        // {
        //     for(int j = 0; j <= n; j++)
        //     {
        //         for(int k = 0; k <= minProfit; k++)
        //         {
        //             dp[i][j][k] = dp[i - 1][j][k];   // 不选i这个位置
        //             if(j - group[i - 1] >= 0)        // k - profit[i - 1]是可以小于0的，因为如果profit[i - 1] > k，说明我们只需要去前i - 1个计划找利润至少为0的即可
        //                 dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
        //             dp[i][j][k] %= mod;
        //         }
        //     }
        // }
        // return dp[len][n][minProfit];
    }
};